<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>快速排序</title>
</head>
<body>
    
</body>
</html>

<script>
    //快速排序的实现
    let tempArr = [81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15];  // 13

    let newArr = [2,1,3];
    function quickSort (arr) {

        //选择枢纽
        function median(left, right) { // 0 12， 
            // 1.求出中间位置
            var center = Math.floor((left + right) / 2) // 6/17， 

            // 2.判断并进行交换
            if(arr[left] > arr[center]) { 
                swap(left, center)
            }
            if(arr[center] > arr[right]) {
                swap(center,right)
            }
            if(arr[left] > arr[right]) {
                swap(left,right)
            }

            // 15, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 81

            // 3.巧妙的操作： 将center 移动到right - 1的位置。
            swap(center, right-1)

            // 15, 94, 11, 96, 12, 35, 75, 95, 28, 58, 41, 17, 81

            // 4.返回privot
            return arr[right - 1]; // 17
        }

        //交换方法
        function swap(m , n) {
            var temp = arr[m];
            arr[m] = arr[n];
            arr[n] = temp;
        }

        function quickSortRen (left, right) {  // 0 12 ， 
            if(left >= right) return;

            // 1.获取枢纽
            var pivot = median(left, right) // 17

            // 开始进行交换

            var i = left; // 0
            var j = right -1; // 11

            while(i < j) {
                while(arr[++i] < pivot) {}; // i=1
                while(arr[--j] > pivot) {}; // j=4

                if(i < j) {
                    swap(i ,j)
                }else {
                    break;
                }
            }

            // 将枢纽放在正确的位置
            swap(i, right-1)

            // 15, 12, 11, 96, 17, 35, 75, 95, 28, 58, 41, 94, 81
            // 递归调用
            quickSortRen(left, i -1); // 0 0
            quickSortRen(i+1, right); // 2 12
        }

        // 快速排序的实现
        quickSortRen(0,arr.length-1); // 0  12

        return arr;
    }

    console.log(quickSort(tempArr))
    console.log(quickSort(newArr))
</script>